% Chapter Template

\chapter{Background} % Main chapter title

\label{Chapter2} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

\lhead{Chapitre 2. \emph{Background}} % Change X to a consecutive number; this is for the header on each page - perhaps a shortened title

%----------------------------------------------------------------------------------------
%	SECTION 1
%----------------------------------------------------------------------------------------

Dans ce chapitre, nous présentons les connaissances de base de la programmation par contrainte : la formulation d'un CSP, comment résoudre un CSP. Quelque notions de consistance de base sont aussi présentées : la consistance de domaine (DC) et les consistances plus faibles que DC tel que \textit{forward checking (FC)} and \textit{bound consistency (BC)}.

\section{Préliminaires}

Un problème de satisfaction de contraintes vise à trouver la solution pour un réseau de contraintes, concrètement, l'assignation des valeurs aux variables doit satisfaire toutes les contraintes. Une contrainte définit une relation entre les variables, elle signifie les combinaisons autorisées des valeurs d'un sous ensemble des variables.
%\textbf{Exemple}

\begin{definition}[CSP]
Un problème de satisfaction de contrainte (CSP) $(X, D(X), C)$ est composé par:
\begin{itemize}
\item un ensemble $X = \{x_1,\dots, x_n\}$ de n variables,
\item un domaine $D(X)= D(x_1)*\dots * D(x_n)$ qui est le produit Cartésien des domaines des variables de $X$,
\item un ensemble de contraintes $C = \{c_1,\dots,c_e\}$ et $vars(c_i) \in X (1 \le i \le e)$
\end{itemize}
\end{definition}

Un CSP est binaire ssi ses contraintes sont binaires. Pour un CSP, on dénote : $n = \#X, e = \#C, d = max_{1\le i \le n}  (\#(D(x)))$ et $k$ comme l'arité  maximum des contraintes.

%\textbf{Exemple}


\begin{definition}[Contrainte]
Une contrainte $c(x_{1},.., x_{k})$ est une relation définie sur les variables $x_{1},\dots, x_{k}$. La contrainte $c$ est dénoté par $(vars(c), rel(c))$ où $vars(c)$ = $\{x_{1},\dots,x_{k}\}$ et $rel(c)$ contient des combinaisons autorisées de valeur pour les variables dans  $vars(c)$. $k$ est l'arité de cette contrainte. Une contrainte avec $k = 2$ est une contrainte binaire.
\end{definition}

Une contrainte peut être définie extensionnellement en donnant une table pour $rel(c)$ ou intentionnellement par une formule ou une expression décrivant $rel(c)$. Deux contraintes $c_i, c_j$ sont \textit{intersectées} ssi $vars(c_i) \cap vars(c_j) \neq \emptyset$.

\begin{example}
La contrainte $c(x_1, x_2, x_3)$ $= \{(2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3),$ $(3, 3, 2)\}$ est définie extensionnellement, elle autorise des tuples qui n'ont que les valeurs 2 et 3. Dans ce cas, $vars(c) = (x_1, x_2, x_3)$ et $(2, 2, 3) \in rel(c)$.\\
La contrainte \textit{allDifferent}$(x_1, x_2, x_3) \equiv (x_1 \neq x_2) \wedge (x_2 \neq x_3) \wedge (x_3 \neq x_1)$ est définie intentionnellement, elle autorise des tuples qui ont des valeurs différentes pour chaque variable.
\end{example}

\begin{definition}[Tuple]
Pour une contrainte $c(x_{1},\dots ,x_{k}) \in C$ 
	\begin{itemize}
	\item Un tuple $\tau \in rel(c)$ est une liste des valeurs en ordre  $(a_{1},\dots,a_{k})$. $\tau$ est considéré comme une assignation des variables $\{(x_1,a_1),\dots, (x_k, a_k)\}$.	
	\item $\tau \in rel(c)$ est \textit{valide} ssi toutes les valeurs dans le tuple sont présentées dans le domaine des variables correspondantes.
	\item Pour un sous ensemble $vars'$ of $vars(\tau)$, $\tau[vars']$ est un sous tuple de $\tau$ qui ne contient que l'assgination aux variables dans $vars'$.
	\item Pour deux tuples $\tau$ et $\tau'$ sur $vars(c) = (x_1, \dots, x_k)$, on peut faire une comparaison lexicographique entre eux : 
	$\tau <_l \tau'$ ssi il existe une sous séquence $(x_1,\dots, x_j)$ de $vars(c)$ tel que $\tau[x_1,\dots,x_j] = \tau'[x_1,\dots,x_j]$ et $\tau[x_{j+1}] <_l \tau'[x_{j+1}]$.
	\end{itemize}
\end{definition}


\begin{definition}[Assignation et solution] Etant donné un CSP $(X, D(X), C)$,
\begin{itemize}
\item Une assignation $s$ sur $vars(s) = \{x_1, \dots, x_k\} \subseteq X$ est présentée par $\{(x_1, a_1), \dots, (x_k, a_k) \}$ où $x_i = a_i$ et $a_i \in D(x_i) (1 \leq i \leq k)$.
\item Une solution partielle est une assignation $s$ telle que $\forall c \in C, vars(c) = \{x_1, \dots, x_k\} \subseteq vars(s)$, $c(a_1, \dots, a_k)$ est satisfaite. Une solution partielle est aussi appelée une assignation localement consistante.
\item Une solution est une solution partielle $s$ avec $vars(s) = X$. L'ensemble de solutions est dénoté  $sol(X, D(X), C)$.
\end{itemize}
\end{definition}

\section{Résolution d'un CSP: Propagation et Recherche}
Pour la résolution d'un CSP, on combine deux techniques : propagation et recherche. La propagation enlève les valeurs impossibles dans la solution, et la recherche trouve la solution. A chaque itération, l'algorithme de recherche choisit une variable et assigne une valeur appropriée à cette variable (branch). Ensuite, la propagation est utilisée pour réduire l'espace de recherche. Cette procédure continue jusqu'à une solution ou un échec. Si cette assignation ne rend pas une solution, on doit revenir en arrière (backtracking) et continuer cette procédure en assignant une autre valeur à cette variable. La résolution finit quand l'espace de recherche est totalement exploitée ou on trouve une solution (ou toutes les solutions).

	\begin{figure}[ht]
	\centering
	\includegraphics[height=6cm]{./images/Search_propagation.png}
	\caption{La résolution d'un CSP : propagation + recherche}
	\label{fig:search_propagation}
	\end{figure}

\subsection{Propagation}
Pour résoudre efficacement un CSP, nous utilisons la propagation. La propagation enlève les valeurs impossibles du domaine de variables pour la solution. Elle permet donc de réduire l'espace de recherche sans enlever la solution. La propagation détecte également les échecs, et termine les branches de l'arbre de recherche, économise l'exploration inutile de l'espace de recherche.

\begin{example}
Etant donné : $D(x)= D(y)= \{1,2,3,4,5\}$ et $c(x,y)= x \geq y + 3$.\\
Un propagateur pour la contraint $c(x,y)= x \geq y + 2$ peut enlever les valeurs 1, 2, 3 de $x$ parce que $x \geq y + 2 \geq 4$. Les valeurs 3, 4, 5 de $y$ sont également enlevées parce que $x \geq y + 3 \Rightarrow y \leq x - 3 \leq 2$. On obtient un CSP équivalent : $D(x) = \{4,5\}, D(y)= \{1,2\} $ et $c(x,y)= x \geq y + 3$.
   
\end{example} 

Différents niveaux d'élagage peuvent être atteints. Ceux-ci sont généralement définies par une propriété de consistance satisfaite par le CSP après la propagation. Un algorithme pour atteindre cette propriété de consistance est utilisé pendant la résolution. Les valeurs qui ne satisfont pas cette propriété sont enlevées par cette algorithme. Si une propriété permet d'enlever plus de valeur, les algorithmes pour elle ont normalement une complexité temporelle plus grande. Il faut trouver un compromis entre les deux.

\subsection{Recherche}

Les problèmes CSP à résoudre sont souvent NP-difficile, la propagation n'est donc pas assez pour ces problèmes. Quand la propagation atteint le but pour chaque nœud (il n'enlève plus de valeur dans le domaine de variables), la recherche trouve une variable et assigne une valeur à cette variable pour continuer.

La recherche est définie par un arbre de recherche et un algorithme pour exploiter cet arbre. Le nœud racine représente le CSP original. Les descendants d'un noeud donné sont obtenus en divisant le CSP, par exemple, la branche binaire : un noeud représente un CSP avec $x = a$ et un autre représente un CSP avec $x \neq a$. Un noeud en échec est un noeud de l'arbre où le CSP a un domaine vide. Un noeud de solution est un noeud de l'arbre où tous les domaine de variables du CSP ont une unique valeur et les contraintes sont satisfaites.

L'algorithme pour exploiter l'arbre de recherche utilise souvent \textit{depth first search} stratégie parce que la complexité de cette stratégie est linéaire avec le nombre de variable. Le CP frammework donc fournit un support pour backtracking. Quand la propagation détecte un noeud en échec (en supprimant des valeurs du domaine de variable), on doit retourner en arrière au noeud précédant et continue exploiter l'arbre de recherche. L'exploitation est arrêtée quand on trouve la solution.\\

\begin{lstlisting}[caption= Resolution d'un CSP : propagation + recherche]
bool Solve(X,D(X),C){
   if |D(x)| == 1 for all x in X {
      return true; // we found a solution!
   } else {
      if (propagation(X,D(X),C) == false) {
         return false;
      } else {
         choose variable x in X with |D(x)| > 1;
         choose element a in D(x);
         return (Solve(X,D(X),C + 'x=a') or Solve(X,D(X),C + 'x$\neq$a')); 
      }
   }
}
\end{lstlisting}

Le code au dessus montre un algorithme pour résoudre un CSP $(X, D(X), C)$. Cet algorithme est récursif et il combine deux étapes : \textit{propagation et recherche}. Son entré est un CSP, cet algorithme nous permet de savoir si ce CSP a une solution. D'abord, si tous les domaines de variables contienne une seul valeur, on trouve une solution (ligne 2-3). Si non, la propagation est appliquée pour enlever les valeurs impossibles. Quand la propagation détecte un domaine vide, la branche est terminée (ligne 5-6). Puis, on fait la recherche (ligne 8-10). Une variable est choisie et une valeur pour cette variable est également choisie (ligne 8-9). Le choix de variable et de valeur peut être réalisé par une heuristique. L'algorithme d'exploitation est une branche binaire : $x = a$ ou $x \neq a$ (ligne 10).

\section{Consistance de domaine (DC)}
Dans la propagation, la consistance la plus utilisée est la consistance de domaine (DC). Cette section présente quelques consistances telles que DC.

\begin{definition}
Pour une contrainte $c \in C$ avec $x \in vars(c)$. Les ensembles de valeur inconsistante et valide pour $x$ dans $c$ par rapport à $D(X)$ sont définis comme suit : 
	\begin{itemize}
	\item $Inc(c,x) = \{(x,a)| a \in D(x) \wedge \forall v \in D(vars(c))_{x=a}: \neg c(v)\}$
	\item $Valid(c,x) = \{(x,a)| a \in D(x) \wedge \forall v \in D(vars(c))_{x=a}: c(v)\}$
	\end{itemize}
	
Nous définissons ensuite :
	\begin{itemize}
	\item $Inc(c) = \bigcup_{x \in vars(c)}Inc(c,x)$
	\end{itemize}
et de même pour l'autre ensemble.
\end{definition}

%Pour une contrainte $c$, $D(vars(c))_{x=a}$ signifie que la variable $x$ est assignée à $a$.

\begin{definition} \textit{Domain consistency (DC)} ou la consistance de domaine
\begin{itemize}
\item Une contrainte c est \textit{domain consistency (DC)} par rapport à $D(X)$ ssi $Inc(c) = \emptyset$ et $\forall x \in X, D(x) \neq \emptyset$.
\item Un CSP $(X, D(X), C)$ est \textit{domain consistency (DC)} ssi toutes ses contraintes sont consistantes de domaine par rapport à $D(X)$.
\end{itemize}
\end{definition}

%\textbf{Generalized Arc Consistency (GAC)}
%	\begin{itemize}
%	\item 
%	A CSP $(X, D(X), C)$ is \textit{generalized arc consistent} iff $\forall x_i \in X, D(x_i)$ is non-empty and $\forall a \in D(x_i), a$ is \textit{GAC-supported} in each constraint $c_j$, s.t. $x_i \in vars(c_j)$.\\
%	A value $a \in D(x_i)$ is \textit{GAC-supported} in a contraint $c_j$ iff $\exists \tau \in rel(c_j)$ such that $\tau[x_i]=a$ and $\tau$ is valid. In this case, we say that $\tau$ is a \textit{GAC-support} of $a$ in $c_j$.
%	\end{itemize}

Dans le cas où les contraintes sont binaires (k=2), \textit{domain consistency} (DC) est appelé \textit{arc consistency (AC)}. Et si les contraintes sont non-binaires, DC est appelé \textit{generalized arc consistency (GAC)}. \textit{Domain consistency} (DC) est souvent utilisé pour résolution d'un CSP. Si une contrainte $c_i$ est DC, alors $\forall x \in vars(c_i), a \in D(x), a$ peut satisfaire la contrainte $c_i$. Autrement dire que $\exists \tau \in rel(c_i)$ telle que $\tau[x] = a$ et $\tau$ est valide. Dans ce cas, $\tau$ est GAC-support de $a$ pour la contrainte $c_i$.

\begin{example} Etant donné $D(x)= D(y)= \{1,2,3,4,5\}$ et $c(x,y)= x \leq y -2$. Alors, on obtient : $Inc(c,x) = \{(x,4), (x,5)\}, Inc(c,y)= \{(y,1), (y,2)\}, Valid(c)= \emptyset$. Si $D(x)=\{1,2,3\}$ et $D(y)= \{3,4,5\}$, la contrainte $c$ est DC. $Valid(c) = \{(x,1), (y,5)\}$.
\end{example}

Pour obtenir DC, plusieurs algorithmes sont proposés. Pour les contraintes binaires, un des algorithmes le plus efficace est AC2001  avec une complexité temporelle de $O(ed^2)$ et une complexité d'espace en $O(ed)$. Pour les contraintes non binaires, un des algorithmes le plus efficace est {GAC2001/3.1} avec une complexité temporelle de $O(ek^2d^k)$ et une complexité d'espace en $O(ekd)$  \cite{bessiere2005optimal}.

%Nous regardons d'abord la \textit{consistance de domaine global}.

\begin{definition}[Consistance de domaine global]
Un CSP $(X, D(X), C)$ est consistent de domaine global ssi : $\forall x_k \in X, \forall a_k \in D(x_k),$ $\exists$ une solution $\{(x_1,a_1),\dots,(x_n, a_n)\} \in Sol(X, D(X), C)$ où $x_k = a_k$.
\end{definition}

L'idée de consistance de domaine global est que chaque valeur de variable appartient à au moins une solution. Imposer la consistance de domaine global est un problème NP-difficile. Au lieu de considérer tous les contraintes, on considère quelques contraintes localement et accomplit la consistance dans ce sous groupe de contraintes. Naturellement, on prend chaque contrainte séparément, et on révise la consistance sur cette contrainte. Dans ce cas, la meilleure propriété de consistance est la consistance de domaine (DC).

%----------------------------------------------------------------------------------------
%	SECTION 2
%----------------------------------------------------------------------------------------
\section{Les consistance plus faibles que DC}

Pour certains problèmes, obtenir la consistance de domaine (DC) est coûteux, on peut considérer la consistance plus faible que DC. La puissance d'élagage de cette consistance est moins forte que celle de DC, par contre, on peut atteindre efficacement cette consistance. Dans cette section, nous présentons deux consistances : \textit{forward checking} et \textit{bound consistency}.

Une consistance $C$ est plus forte que l'autre consistance $C'$ (ou $C'$ est plus faible que $C$) ssi un CSP est $C$ $\Rightarrow$ il est aussi $C'$. Par conséquence, si $C$ est plus forte que $C'$, un algorithme quelconque pour $C$ enlève au moins les valeurs qu'un algorithme pour $C'$ enlève. Une consistance $C$ est strictement plus forte que l'autre consistance $C'$ (ou $C'$ est strictement plus faible que $C$), s'il existe un CSP qui est $C'$ mais il n'est pas $C$ \cite{debruyne2001domain}.
%%-----------------------------------
%%	SUBSECTION 1
%%-----------------------------------
\subsection{Forward Checking (FC)}
\begin{definition}[Forward Checking] 
Une contrainte $c(x_1,\dots, x_k)$ est \textit{Forward Checking (FC)} par rapport à $D(X)$ ssi
%\begin{center}
$\exists y \in vars(c), \forall x \in vars(c) \setminus \{y\}: \#D(x) = 1$ $\Rightarrow$ $c$ est domaine consistant (DC).
%\end{center}
Un CSP $(X, D(X), C)$ est \textit{Forward Checking (FC)} ssi toutes ses contraintes sont \textit{FC} par rapport à $D(X)$.
\end{definition}

Un CSP est FC si les valeurs assignées sont une solution partielle, et toutes les contraintes que ses variables sont assignées sauf une sont DC. Pour obtenir FC, un algorithme est proposé dans \cite{bessiere2006constraint} avec une complexité temporelle de $O(ed)$ et complexité d'espace en $O(e)$. Un algorithme pour FC est normalement plus rapide que celui pour DC. Dans le cas où atteindre DC est coûteux, on peut considérer FC.

\begin{example} Etant donné la contraint $c = 3x-2y-z \neq 4$. Si $D(x)= \{1,2,3\}, D(y)=\{1,2\}, D(z)=\{3\}$, alors $c$ est FC. Si $D(x)= \{1,2,3\}, D(y)=\{\textbf{1}\}, D(z)=\{\textbf{3}\}$, alors $c$ n'est pas FC. L'application de FC: $D(x)= \{1,2\}, D(y)=\{1\}, D(z)=\{3\}$.
\end{example}

%%-----------------------------------
%%	SUBSECTION 2
%%-----------------------------------
\subsection{Bound Consistency (BC)}
\begin{definition}
Etant donné un CSP $(X, D(X), C)$, on définit $D^*(X) = D^*(x_1) *\dots D^*(x_n)$, avec $D^*(x)= [min(D(x)), max(D(x))]$
\end{definition}

\begin{definition}[Bound Consistency] Une contrainte $c(x_1,\dots, x_k)$ est \textit{Bound Consistency (BC)} par rapport à $D(X)$ ssi 
%\begin{center}
$\forall x \in vars(c)$, $\forall a \in \{min(D(x)), max(D(x))\}: (x,a) \notin Inc(c,x, D^*(X))$.
%\end{center}
Un CSP $(X, D(X), C)$ est \textit{Bound Consistency (BC)} ssi toutes ses contraintes sont \textit{BC} par rapport à $D(X)$.
\end{definition}

BC consiste à détecter les valeurs inconsistances dans la borne (min et max) du domaine de variables. BC assure que les valeurs minimum et maximum d'un domaine d'une variable peuvent satisfaire des contraintes portant sur cette variable. Pour obtenir BC, dans \cite{bessiere2006constraint}, l'auteur a décrit un algorithme avec une complexité temporelle de $O((d^*)^{2})$, $d^*$ est la taille la plus grande du domaine $D^*$.

\begin{example} Etant donné les domaines : $D(x)= \{2,3,4\}, D(y)=D(z)=\{2,4\}$. La contrainte $c = x+y+z=10$ est BC mais n'est pas DC car $(x,3)$ n'a pas de support.
\end{example}
